package leetcode.graph.bfs.p773;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 
 * @Title: Solution_v1.java 
 * @Package leetcode.graph.bfs.p773 
 * @Description: 773. 滑动谜题
 *                  将二维数组构成的面板解析为一个整型数字
 * @author CandyWall   
 * @date 2021年1月18日 下午3:57:54 
 * @version V1.0
 */
class Solution_v1 {
    public int slidingPuzzle(int[][] board) {
        if(boardToInt(board) == 123450) {
            return 0;
        }
        boolean[] visited = new boolean[1000_000];
        int[] distances = new int[1000_000];
        Queue<Integer> queue = new LinkedList<>();
        int firstPuzzleNum = boardToInt(board);
        queue.add(firstPuzzleNum);
        visited[firstPuzzleNum] = true;
        while(!queue.isEmpty()) {
            int num = queue.remove();
            for(int nextNum : nextNums(num)) {
                if(!visited[nextNum]) {
                    queue.add(nextNum);
                    visited[nextNum] = true;
                    distances[nextNum] = distances[num] + 1;
                    // 如果结果是123450，就结束搜索，返回移动次数
                    if(nextNum == 123450) {
                        return distances[nextNum];
                    }
                }
            }
        }
        
        return -1;
    }
    
    // 根据当前面板上面的数字序列滑动一次后可能出现的数字数列
    private ArrayList<Integer> nextNums(int num) {
        ArrayList<Integer> res = new ArrayList<>();
        int[][] board = intToBoard(num);
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 3; j++) {
                // 找到面板中0的位置
                if(board[i][j] == 0) {
                    // 跟其他位置交换
                    int[][] dirs = {{0, -1}, {1, 0}, {0, 1} ,{-1, 0}};
                    for(int d = 0; d < 4; d++) {
                        int nextI = i + dirs[d][0];
                        int nextJ = j + dirs[d][1];
                        if(inArea(nextI, nextJ)) {
                            // 交换两个位置的元素
                            swap(board, i, j, nextI, nextJ);
                            // 记录交换后的结果
                            res.add(boardToInt(board));
                            // 面板复位，为寻找下一种可能性做准备
                            swap(board, i, j, nextI, nextJ);
                        }
                    }
                }
            }
        }
        return res;
    }
    
    // 交换数组中的两个元素
    private void swap(int[][] board, int i, int j, int nextI, int nextJ) {
        int temp = board[i][j];
        board[i][j] = board[nextI][nextJ];
        board[nextI][nextJ] = temp;
    }

    // 判断二维数组的索引是否合法
    private boolean inArea(int x, int y) {
        return x >= 0 && x < 2 && y >= 0 && y < 3;
    }

    // 将当前整型数字转成6位数字的面板
    private int[][] intToBoard(int num) {
        int[][] board = new int[2][3];
        for(int k = 0; k < 6; k++) {
            int i = k / 3, j = k % 3;
            int m = 1;
            for(int l = 1; l < 6 - k; l++) {
                m *= 10;
            }
            board[i][j] = num / m;
            num %= m;
        }
        return board;
    }

    // 将包含6个数字的面板转成一个6位的整型数字
    private int boardToInt(int[][] board) {
        int num = 0;
        for(int k = 0; k < 6; k++) {
            int i = k / 3, j = k % 3;
            int m = board[i][j];
            for(int l = 1; l < 6 - k; l++) {
                m *= 10;
            }
            num += m;
        }
        return num;
    }
    
    public static void main(String[] args) {
        System.out.println(new Solution_v1().boardToInt(new int[][] {{1, 2, 3}, {5, 4, 0}}));
        int[][] board = new Solution_v1().intToBoard(123540);
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 3; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println(new Solution_v1().slidingPuzzle((new int[][] {{1, 2, 3}, {5, 4, 0}})));
        System.out.println(new Solution_v1().slidingPuzzle((new int[][] {{1, 2, 3}, {4, 0, 5}})));
        System.out.println(new Solution_v1().slidingPuzzle((new int[][] {{4, 1, 2}, {5, 0, 3}})));
        System.out.println(new Solution_v1().slidingPuzzle((new int[][] {{1, 2, 3}, {4, 5, 0}})));
    }
}